/**
 * 53. Maximum Subarray 最大子数组和
 * https://leetcode.com/problems/maximum-subarray/
 */
class MaximumSubarray {
    /**
     * 方法：动态规划
     * Args: int[] nums - 输入数组
     * Returns: int - 最大子数组和
     * Time: O(n) - 只需遍历数组一次
     * Space: O(1) - 只使用了常数个额外空间
     */
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int f = 0;
        for(int x: nums){
            f = Math.max(f, 0) + x;
            ans = Math.max(f, ans);
        }
        return ans;
    }

     /**
     * 方法：前缀和
     * Args: int[] nums - 输入数组
     * Returns: int - 最大子数组和
     * Time: O(n) - 只需遍历数组一次
     * Space: O(1) - 只使用了常数个额外空间
     */
    public int maxSubArray1(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int minPreSum = 0, preSum = 0;
        for(int x: nums){
            preSum += x;
            ans = Math.max(ans, preSum - minPreSum);
            minPreSum = Math.min(minPreSum, preSum);
        }
        return ans;
    }
}